package javaDemo;

/**
 * @author hewei8<br>
 * Date 2019年2月14日<br>
 * <p>斐波那契数列</p>
 * 1,1,2,3,5,.......
 * 
 * 
 * 
 */
public class Fibonacci {
	
	// 迭代方法，效率高
	public static long Fibonacci_died(int number) {
		if (number <= 0) {
			return 0;
		}
		if (number == 1 || number == 2) {
			return 1;
		}
		int first = 1, second = 1, third = 0;
		for (int i = 3; i <= number; i++) {
			third = first + second;
			first = second;
			second = third;
		}
		return third;
	}
	
	// 递归方法，效率低
	public static long Fibonacci_dg(int n) {
        
		if (n <= 0) {
			return 0;
		}
		if (n == 1||n==2) {
			return 1;
		}

		return Fibonacci_dg(n - 2) + Fibonacci_dg(n - 1);

	}
	
	public static void main(String[] args) {
		
		System.out.println("1,1,2,3,5,.......");
		int number=6;
		
		Long begin=System.currentTimeMillis();
		long n=Fibonacci.Fibonacci_dg(number);
		System.out.println(n+":"+(System.currentTimeMillis()-begin));
		
		Long begin1=System.currentTimeMillis();
		long n1=Fibonacci.Fibonacci_died(number);
		System.out.println(n1+":"+(System.currentTimeMillis()-begin1));
	}

}
